package twice.class_digui;

import java.util.HashMap;

public class Class08_StickersToSpellWord {
    public static int minStickers1(String[] stickers, String target){
        int ans = process1(stickers, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    public static int process1(String[] stickers,String target){
        if(target.length()==0){
            return 0;
        }
        int min = Integer.MAX_VALUE;
        for(String s : stickers){
            String rest = minus(target,s);
            if(rest.length() != target.length()){
                min = Math.min(min,process1(stickers,rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }
    public static String minus(String target,String s){
        char[] a = target.toCharArray();
        char[] b = s.toCharArray();
        int[] count = new int[26];
        for(int i = 0;i < a.length;i++){
            count[a[i] - 'a']++;
        }
        for(int i = 0;i < b.length;i++){
            count[b[i] - 'a']--;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < 26;i++){
            if(count[i] > 0){
                for (int j = 0; j < count[i]; j++) {
                    sb.append((char) (i + 'a'));
                }
            }
        }
        return sb.toString();
    }

    public static int minStickers2(String[] stickers, String target){
        int[][] count = new int[stickers.length][26];
        for(int i = 0;i < stickers.length;i++){
            char[] a = stickers[i].toCharArray();
            for(int j=0;j < a.length;j++){
                count[i][a[j] - 'a']++;
            }
        }
        int ans = process2(count, target);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    public static int process2(int[][] stickers,String target){
        if(target.length()==0){
            return 0;
        }
        char[] t = target.toCharArray();
        int[] tcounts = new int[26];
        for (char cha : t) {
            tcounts[cha - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < stickers.length;i++){
            int[] a = stickers[i];
            if(a[t[0]-'a'] > 0){
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    if (tcounts[j] > 0) {
                        int nums = tcounts[j] - a[j];
                        for (int k = 0; k < nums; k++) {
                            builder.append((char) (j + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                min = Math.min(min,process2(stickers,rest));
            }
        }
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }

    public static int minStickers3(String[] stickers, String target){
        int[][] count = new int[stickers.length][26];
        for(int i = 0;i < stickers.length;i++){
            char[] a = stickers[i].toCharArray();
            for(int j=0;j < a.length;j++){
                count[i][a[j] - 'a']++;
            }
        }
        HashMap<String,Integer> dp = new HashMap<>();
        int ans = process3(count, target,dp);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    public static int process3(int[][] stickers,String target,HashMap<String,Integer> dp){
        if(dp.containsKey(target)){
            return dp.get(target);
        }
        if(target.length()==0){
            dp.put(target,0);
            return 0;
        }
        char[] t = target.toCharArray();
        int[] tcounts = new int[26];
        for (char cha : t) {
            tcounts[cha - 'a']++;
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < stickers.length;i++){
            int[] a = stickers[i];
            if(a[t[0]-'a'] > 0){
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    if (tcounts[j] > 0) {
                        int nums = tcounts[j] - a[j];
                        for (int k = 0; k < nums; k++) {
                            builder.append((char) (j + 'a'));
                        }
                    }
                }
                String rest = builder.toString();
                min = Math.min(min,process3(stickers,rest,dp));
            }
        }
        dp.put(target,min + (min == Integer.MAX_VALUE ? 0 : 1));
        return min + (min == Integer.MAX_VALUE ? 0 : 1);
    }
}
